package 蓝桥杯算法;

import 二叉树.TreeNode;
import 队列.LinkedListQueue;

import java.util.*;


public class day14 {
    public static void main(String[] args) {
        int[] arr1={9,3,15,20,7};
        int[] arr2={9,15,7,20,3};
        day14 a=new day14();
         TreeNode root=a.buildTree(arr1,arr2);

        TreeNode root1=a.MaxTree(arr1,0, arr1.length-1);
       /* a.loop(root1);*/
        List<List<Integer>> resylt=a.combaine1(6,2);
        System.out.println(resylt.toString());




    }
    public void loop(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left!=null){
            loop(root.left);
        }

        System.out.println(root.val);

        if(root.right!=null){
            loop(root.right);
        }

    }
    Map<Integer,Integer> map;//存储好位置，方便寻找
    public TreeNode  buildTree(int[] inorder,int[] postorder){
        map=new HashMap<>();
        for(int i=0;i<postorder.length;i++){
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    public TreeNode findNode(int[] inorder,int instart,int inend,int[] postorder,int poststart,int postend){
        if(instart>=inend||postend<=poststart){
            return null;
        }
        int rootIndex=map.get(postorder[postend-1]);
        TreeNode root=new TreeNode(inorder[rootIndex]);//找到根节点
        int lenofLef=rootIndex-instart;
        root.left=findNode(inorder,instart,rootIndex,postorder,poststart,poststart+lenofLef);
        root.right=findNode(inorder,rootIndex+1,inend,postorder,poststart+lenofLef,postend-1);
        return root;
    }
    Map<Integer,Integer> map2;
    public TreeNode MaxTree(int[] arr,int start,int end){
       if(end<=start){
           return null;
       }
        int index=0;
        int max=0;
        for(int i=start;i<end;i++){
            if(max<arr[i]){
                max=arr[i];
                index=i;
            }
        }
        TreeNode root=new TreeNode(max);
        root.left=MaxTree(arr,start,index);
        root.right=MaxTree(arr,index+1,arr.length);
        return root;
        }
        List<List<Integer>> result=new ArrayList<>();
        LinkedList<Integer> path=new LinkedList<>();

      /*  public List<List<Integer>> combaine(int n, int k){//组合问题
            backtracking(n,k,1);
            return result;
    }
         public void backtracking(int n,int k,int start){
            if(path.size()==k){
                result.add(new ArrayList<>(path));
                return;
            }
            for(int i=start;i<=n;i++){
                path.add(i);
                backtracking(n,k,i+1);
                path.removeLast();//删除的是最后一个
            }


    }*/
    public List<List<Integer>> combaine1(int n,int k){//此次回溯涉及sum的加减
            backtracking1(n,k,1,0);
            return result;
    }
    public void backtracking1(int target,int k,int start,int sum){
            if(sum>target){
                return;
            }
            if(sum==target&&path.size()==k){
                result.add(new ArrayList<>(path));
                return;
            }

            for(int i=start;i<=9;i++){
                path.add(i);
                sum+=i;
                backtracking1(target,k,i+1,sum);
                path.removeLast();
                sum-=i;
            }
    }
    List<String> result2=new ArrayList<>();
    public List<String> combaine2(String str){
        if(str==null||str.length()==0){
            return result2;
        }
        String[] numStr={"","","abc","def","ghi","jkl","mno","pqs","tuv","wxyz"};
        backTracking(str,numStr,0);
        return result2;
    }
    StringBuilder temp=new StringBuilder();
    public void backTracking(String str,String[] Str,int num){
        if(num==str.length()){
            result2.add(temp.toString());
            return;
        }
   String str1=Str[str.charAt(num)-'0'];
        for(int i=0;i<str1.length();i++){
            temp.append(str1.charAt(i));
            backTracking(str,Str,num+1);
            temp.deleteCharAt(temp.length()-1);
        }
    }


}
